package 链表;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/linked-list-cycle-ii/
 */
public class _142_环形链表II {

    /**
     * 快慢指针
     * 解法 ：
     * 一共有三段 ：a(不循环的路段) b(相遇时a在环内的路段) c(总环内路段 - a在环内的路段)
     * fast和slow相遇时fast所走的路段是：a + n * (b + c) + b ->  a + (n + 1) * b + n * c
     * 因为fast是slow的两倍  所以  fast的路段也等于 2 * (a + b)
     * 即 a + (n + 1) * b + n * c = 2 * (a + b)
     *                      --> a = (n - 1) * b + n * c
     *                      --> a = (n - 1) * (b + c) + c
     * 因为 b + c 是总环内路段 则a的距离正好等于slow移动c的距离
     * 即 当新节点从head开始走，当遇到slow节点时，正好在循环点处
     * @param head 目标链表
     * @return ListNode
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            slow = slow.next;
            // 如果fast.next为null 则不为闭环
            if (fast.next != null) {
                fast = fast.next.next;
            }else {
                return null;
            }
            // 如果相同 则计算闭环初始位置
            if (slow == fast) {
                ListNode ptr = head;
                while(ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

    /**
     * 使用哈希表 进行存储 遍历 判断   不推荐使用 时间复杂度：O(n) 空间复杂度 O(n)
     * @param head 目标链表
     * @return ListNode
     */
    public ListNode detectCycleBySet(ListNode head) {
        Set<ListNode> cache = new HashSet<>();
        ListNode tail = head;
        while (tail != null) {
            if (!cache.contains(tail)) {
                cache.add(tail);
                tail = tail.next;
            } else {
                return tail;
            }
        }
        return null;
    }
}
